package BinarySearch;

/*
找到 K 个最接近的元素
给定一个 排序好 的数组arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b

示例 1：
输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]
示例 2：
输入：arr = [1,1,2,3,4,5], k = 4, x = -1
输出：[1,1,2,3]

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/binary-search/xeve4m/
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class _42找到K个最接近的元素 {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        List<Integer> closestElements = findClosestElements(arr,4,3);
        closestElements.forEach(System.out::println);

    }

    //超时
    //原因： 多次使用二分查找 并且最终还要对查找结果进行二次判断
    //优化: 只进行一次二分查找，找到最可能接近的index,然后循环K次判断 添加  差不多官解二 的思路
    public static List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> res = new ArrayList<Integer>();
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }
        for (int i = 0; i < k; i++) {
            int left = 0, right = list.size() - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (list.get(mid) == x) {
                    left = mid;
                    break;
                } else if (list.get(mid) < x) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            if(Math.abs(list.get(left) - x) < Math.abs(list.get(left + 1) - x)) {
                res.add(list.get(left));
                list.remove(left);
            }else {
                res.add(list.get(left + 1));
                list.remove(left + 1);
            }
        }
        Collections.sort(res);
        return res;
    }

    //官解：自定义排序
    class Solution {
        public List<Integer> findClosestElements(int[] arr, int k, int x) {
            List<Integer> list = new ArrayList<Integer>();
            for (int num : arr) {
                list.add(num);
            }
            //                      o1 为变量  o2 为定值
            Collections.sort(list, (a, b) -> {
                if (Math.abs(a - x) != Math.abs(b - x)) {
                    // 距离差值 >0  将o1排o2后面
                    return Math.abs(a - x) - Math.abs(b - x);
                } else {
                    return a - b;
                }
            });
            //截取
            List<Integer> ans = list.subList(0, k);
            Collections.sort(ans);
            return ans;
        }
    }

    //官解：二分查找 + 双指针动态区间
    class Solution2 {
        public List<Integer> findClosestElements(int[] arr, int k, int x) {
            int right = binarySearch(arr, x);
            int left = right - 1;
            while (k-- > 0) {
                if (left < 0) {
                    right++;
                } else if (right >= arr.length) {
                    left--;
                } else if (x - arr[left] <= arr[right] - x) {
                    left--;
                } else {
                    right++;
                }
            }
            List<Integer> ans = new ArrayList<Integer>();
            for (int i = left + 1; i < right; i++) {
                ans.add(arr[i]);
            }
            return ans;
        }

        public int binarySearch(int[] arr, int x) {
            int low = 0, high = arr.length - 1;
            while (low < high) {
                int mid = low + (high - low) / 2;
                if (arr[mid] >= x) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
            return low;
        }
    }

}
